package org.shj.dhsjjg.minpath;

/**
 * 费洛伊德算法解决与Dijkstra相同的问题。区别是本算法算出所有顶点与其它顶点的最短路径
 * @author huangjian
 *
 */
public class Floyd {

	public static int M = Integer.MAX_VALUE;
	
	public static void main(String[] args){
		int[][] graph = init();     //把图的信息初始化为一个二维数组
		int MaxVex = graph.length;  //图中顶点的个数
		int[][] pathMatrix = new int[MaxVex][MaxVex];  //每一列的数值的意思同Dijkstra 算法中的 pathMatrix[] 相同
		int[][] shortPath = new int[MaxVex][MaxVex];
		int v,w,k;
		
		for(v = 0 ; v < MaxVex; v++){     //初始化 D 与 P，见图Floyd.png
			for(w = 0 ; w < MaxVex; w++){
				shortPath[v][w] = graph[v][w];
				pathMatrix[v][w] = w;
			}
		}
		
		for(k = 0 ; k < MaxVex; ++k){  //k -- 所有的顶点都通过 k点中转
			for(v = 0; v < MaxVex; ++v){ //v -- 起始点
				for(w = 0 ; w < MaxVex; ++w){ //w -- 结束点
					if(shortPath[v][k] != M && shortPath[k][w] != M && shortPath[v][w] > shortPath[v][k] + shortPath[k][w]){ //经过下标为k顶点的路径比原两点间路径更短
						shortPath[v][w] = shortPath[v][k] + shortPath[k][w]; //将当前两点间权值设为昜小的一个
						pathMatrix[v][w] = pathMatrix[v][k];    //路径设置经过下标为k的顶点
					}
				}
			}
		}
		
		//示例打印V0到V8的最短路径, 此例中pathMatrix[0][8] = 1, 知需经过V1顶点，再由 pathMatrix[1][8]的值得知下一个需要经过的顶点... 直至V8顶点
		int begin = 0;
		int end = 8;
		while( begin != end){
			System.out.print("V" + begin + "-->");
			begin = pathMatrix[begin][end];
		}
		System.out.print("V" + end);
	}
	
	//把图的信息初始化成一个二维数组，用极大值M代表两点之间无直接连线, 
	private static int[][] init(){
		return new int[][]{
				{0, 1, 5, M, M, M, M, M, M},
				{1, 0, 3, 7, 5, M, M, M, M},
				{5, 3, 0, M, 1, 7, M, M, M},
				{M, 7, M, 0, 2, M, 3, M, M},
				{M, 5, 1, 2, 0, 3, 6, 9, M},
				{M, M, 7, M, 3, 0, M, 5, M},
				{M, M, M, 3, 6, M, 0, 2, 7},
				{M, M ,M, M, 9, 5, 2, 0, 4},
				{M, M, M, M, M, M, 7, 4, 0}
				
		};
	}
}
